package com.computer.fundamentals.algorithm;



/**
 * 经典问题——整数拆分
 * (原版: 限定划分的最大值下的最大方案数)
 *  -----------------------------------------------------------------------------------------------
 *  所谓整数划分，是指把一个正整数n写成如下形式：
 *  n=m1+m2+m3+....+mi;（其中mi为正整数，并且1<=mi<=n），则{m1,m2,m3,....,mi}为n的一个划分。
 *  如果{m1,m2,m3,....,mi}中的最大值不超过m，即max{m1,m2,m3,....,mi} <= m，则称它属于n的一个m划分。
 *  这里我们记n的m划分的个数为f(n,m)；
 *  例如当n=4时，它有5个划分：{4}、{3,1}、{2,2}、{2,1,1}、{1,1,1,1}；
 *
 *  注意：4=1+3和4=3+1被认为是同一个划分。
 *  该问题是求出n的所有划分个数，即f(n,m)。下面我们考虑求f(n,m)的方法。
 *  -----------------------------------------------------------------------------------------------
 *
 * (改版：限定划分个数下的最大方案数)
 *  -----------------------------------------------------------------------------------------------
 *  将整数n分成k份，且每份不能为空，任意两个方案不能相同(不考虑顺序)。
 *
 *  例如：n=7，k=3，下面三种分法被认为是相同的。
 *  1，1，5;
 *  1，5，1;
 *  5，1，1;
 *  问有多少种不同的分法。
 *
 *  输入：n，k ( 6 < n ≤ 200，2 ≤ k ≤ 6 )
 *  输出：一个整数，即不同的分法
 *  -----------------------------------------------------------------------------------------------
 */
public class IntegerPartition {

    public int[][] originalDFSMemory;
    public int n;
    public int m;

    public IntegerPartition(int n, int m) {
        this.n = n;
        this.m = m;
        originalDFSMemory = new int[n+1][m+1];
    }

    /**
     * 解决方案(原版)：
     *  方案一：记忆化递归
     *      1. 当n=1时, 不论m的值为多少(m>0), 只有一种划分, 即{1}
     *      2. 当m=1时, 不论n的值为多少(n>0), 只有一种划分, 即{1,1,1...1}
     *      3. 当n=m时, 需要分为两种情况
     *          ① 包含n的情况, 如果包含n, 那么只有一种情况, 即{n}
     *          ② 不包含n的情况, 那么就相当于所有数都小于n, 即为f(n, n-1)的划分数
     *      4. 当n<m时, 由于不能切割成小于1的数, 因此就相当于f(n, n)
     *      5. 当n>m时, 此时有两种情况：
     *          ① 包含m, 如果包含m, 那么则有f(n-m, m)个切分方式, 因为除掉m后仍有可能包含m
     *          ② 不包含m, 那么说明所有数都小于m, 即有f(n, m-1)种切分方式
     *      综上，根据所有情况, 并限定m和n的范围(n >= 1, m >= 1), 编写递归代码, 为了加快效率, 还可以添加记忆化数组剪枝
     */
    public int originalEditionDFS(int n, int m) {
        if (n <= 0) {
            return 0;
        }
        if (originalDFSMemory[n][m] != 0) {
            return originalDFSMemory[n][m];
        }
        if (n == 1 || m == 1) {
            originalDFSMemory[n][m] = 1;
            return originalDFSMemory[n][m];
        }

        if (n == m) {
            originalDFSMemory[n][m] = 1 + originalEditionDFS(n, n-1);
        } else if (n < m) {
            originalDFSMemory[n][m] = originalEditionDFS(n, n);
        } else { // n > m
            originalDFSMemory[n][m] = originalEditionDFS(n-m, m) + originalEditionDFS(n, m-1);
        }

        return originalDFSMemory[n][m];
    }

    /**
     * 解决方案(原版)：
     *  方案二：动态规划
     *  类似递归法, 但是自底向上的
     */
    public int originalEditionDP(int n, int m) {
        int[][] dp = new int[n+1][m+1];
        for (int i = 1;i <= n;i++) {
            for (int j = 1;j <= m;j++) {
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                }else {
                    if (i == j) {
                        dp[i][j] = dp[i][j-1] + 1;
                    }else if (i < j) {
                        dp[i][j] = dp[i][i];
                    }else if ((i - j) < j) {
                        dp[i][j] = dp[i-j][i-j] + dp[i][j-1];
                    }else {
                        dp[i][j] = dp[i-j][j] + dp[i][j-1];
                    }
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 解决方案(改版)
     *  令 f[i][j] 表示 "数 i 被划分成 j 份的分法", 6 < i <= 200, 2 <= j <= 6，求解目标为 f[n][k]。
     *  对于整数 i, 如果需要划分为 j 份, 首先每一份的值必然不为 0, 故恒有 j <= i, 即每份的最小值为 1,
     *  剩下的值为 i - j, 而这个 i - j 我们可以全部放到 j 份中的任意一份, 对应的是 f[i - j][1](将数 i - j 划分成 1 份)
     *  也可以是其中 2, 3, ...(f[i - j][2, 3...])份, 这时候我们已经构建出了一个递推关系, 也就可以开始求状态转移方程了
     *
     *  依上述关系，可得：
     *  ① f[i][j] = f[i - j][1] + f[i - j][2] + ... f[i - j][j]
     *  ② f[i - 1][j - 1] = f[i - j][1] + f[i - j][2] + ... + f[i - j][j - 1]
     *  将 ② 式代入 ① 式，可得：
     *  f[i][j] = f[i - j][j] + f[i - 1][j - 1] ③，即状态转移方程。
     */
    public int revision(int n, int k) {
        int[][] dp = new int[n+1][k+1];
        for (int i = 1;i <= n;i++) {
            dp[i][1] = 1;
            for (int j = 2;j <= Math.min(i, k);j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            }
        }
        return dp[n][k];
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        IntegerPartition integerPartition = new IntegerPartition(200, 20);
        System.out.println("------------测试------------");
        System.out.println("------------原版递归法测试------------");
        System.out.println(integerPartition.originalEditionDFS(integerPartition.n, integerPartition.m));
        System.out.println("------------原版动态规划测试------------");
        System.out.println(integerPartition.originalEditionDP(integerPartition.n, integerPartition.m));
        System.out.println("\n");

        System.out.println("------------改版动态规划测试------------");
        System.out.println(integerPartition.revision(7, 3));

    }

}